Un réseau professionnel (2) - Corrigé

Énoncé

Anna, Benjamin, Colin, Dana, Étienne, François, Giselle, Hadrien, Inès, Jasmine, Kévin et Lola sont tous inscrits sur le même réseau professionnel.

Voici leurs liens relationnels :

• Anna est en relation avec Benjamin et Inès.
• Benjamin est en relation avec Anna, Lola, Jasmine et Hadrien.
• Dana est en relation avec Colin, Étienne et François.
  
• Giselle est en relation avec Colin et François.
• Lola est en relation avec Benjamin, Hadrien et Kévin.

1. Représenter ces relations avec un graphe (on pourra utiliser les initiales des prénoms).

2. Ce graphe est-il connexe ?

3. Peut-on trouver une chaîne qui lie Inès et Kévin ? Si oui, en écrire une.

4. Dana a vu une annonce de stage dans l'entreprise de Kévin. Elle aimerait rentrer en contact avec lui. Peut-on trouver une chaîne qui les lie ? Si oui, en écrire une.

5. Colin a rencontré Inès à un séminaire et rentre en relation avec elle. Cela permettra-t-il à Dana d'entrer en contact avec Kévin ? Autrement dit, peut-on trouver à présent une chaîne qui les lie ? Quelle est la distance entre Anna et Kévin ?

Solution

1. Graphe des relations :

2. Ce graphe n'est pas connexe. Il n'existe par exemple par de chaîne liant Benjamin et Colin. Ce graphe a deux composantes connexes {A, B, H, I, J, K, L} et {C, D, E, F, G}.

3. Oui, on peut relier Inès et Kévin, par exemple avec la chaîne Inès - Anna - Benjamin - Lola - Kévin.

4. Non, il n'existe pas de chaîne qui lie Dana et Kévin, car ils sont sur deux composantes connexes différentes du graphe.

5. On ajoute une arête Colin - Inès au graphe. 
Le nouveau graphe ainsi constitué est alors connexe, et il devient possible pour Dana d'entrer en relation avec Kévin. Une chaîne possible est alors : Dana - Colin - Inès -  Anna - Benjamin - Lola - Kévin.